import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        int cnt=0;
        while(cnt<t){
            int n=sc.nextInt();
            int q=sc.nextInt();
            int[] arr=new int[n];
            for(int i=0;i<n;i++){
                arr[i]=sc.nextInt();
            }
            int num=0;
            while(num<q){
                int cou=0;
                int l=sc.nextInt();
                int r=sc.nextInt();
                for(int i=l-1;i<r;i++){
                    if(isNum(arr[i])){
                        cou++;
                    }
                }
                System.out.println(cou);
                num++;
            }
            cnt++;
        }
    }
    public static boolean isNum(int num){
        int count=0;
        for(int i=1;i<=Math.sqrt(num);i++){
            if(num%i==0){
                if(i!=num/i){
                    count+=i+num/i;
                }else{
                    count+=i;
                }
            }
        }
        if((num*count)%2==0){
            return true;
        }
        return false;
    }
}